package com.ze.java.datastructure.other;

import java.util.Random;
import java.util.Stack;

/**
 * 跳表
 *
 * @Author:yangzy
 * @Date:2021/4/1 11:08
 */
public class SkipList<T> {
    SkipNode<T> head;
    int curLevel;
    Random random;
    final int max_level = 32;

    public SkipList() {
        random = new Random();
        curLevel = 0;
        head = new SkipNode<>(Integer.MIN_VALUE, null);
    }

    public SkipNode search(int key) {
        SkipNode team = head;
        while (team != null) {
            if (team.key == key) {
                return team;
            } else if (team.right == null) {
                team = team.down;
            } else if (team.right.key <= key) {
                team = team.right;
            } else if (team.right.key > key) {
                team = team.down;
            }
        }
        return null;
    }

    public void delete(int key) {
        SkipNode team = head;
        while (team != null) {
            if (team.right == null) {
                team = team.down;
            } else if (team.right.key == key) {
                team.right = team.right.right;
                team = team.down;
            } else if (key > team.right.key) {
                team = team.right;
            } else {
                team = team.down;
            }
        }
    }

    public void add(SkipNode<T> node) {
        int key = node.key;
        //判断当前key值是否存在, 有做value更新
        SkipNode findNode = this.search(key);
        if (findNode != null) {
            findNode.value = node.value;
            return;
        }
        /**
         * 找出插入各层的位置, 存储与栈中
         */
        Stack<SkipNode<T>> downStack = new Stack<>();
        SkipNode team = head;
        while (team != null) {
            if (team.right == null) { //右侧无节点往下找
                downStack.add(team);
                team = team.down;
            } else if (team.right.key > key) { //右侧节点值大于待插入节点往下找
                downStack.add(team);
                team = team.down;
            } else {
                team = team.right;
            }
        }

        //插入，第一层必须插入  上面层级按random判断是否插入
        int level = 1;
        SkipNode<T> lastDown = null;
        while (!downStack.isEmpty()) {
            SkipNode leftNode = downStack.pop();
            SkipNode newNode = new SkipNode(node.key, node.value);
            if (leftNode.right == null) {
                leftNode.right = newNode;
            } else {
                newNode.right = leftNode.right;
                leftNode.right = newNode;
            }
            newNode.down = lastDown;
            lastDown = newNode;
            //层级答到最大
            if (level > max_level) {
                break;
            }
            //根据随机判断是否执行插入
            double num = random.nextDouble();//[0-1]随机数
            if (num > 0.5) {
                break;
            }
            level++;
            //层级大于跳表最大层级
            if (level > curLevel) {
                curLevel = level;
                SkipNode<T> newHead = new SkipNode<>(Integer.MIN_VALUE, null);
                newHead.down = head;
                head = newHead;
                downStack.add(head);
            }
        }
    }

    public static void printSkipList(SkipNode head) {
        SkipNode bottomHead = head;
        while (bottomHead.down != null) {
            bottomHead = bottomHead.down;
        }

        SkipNode term = head;
        SkipNode headDown = head.down;
        while (term != null) {
            System.out.print(toNodeString(term));
            if (term.right != null) {
                System.out.print("——>");
                term = term.right;
            } else {
                term = headDown;
                if (headDown != null) {
                    headDown = headDown.down;
                }
                System.out.println();
            }
        }
    }

    public static String toNodeString(SkipNode<String> node) {
        if (node == null) {
            return "";
        } else {
            if (node.key == Integer.MIN_VALUE) {
                return "head";
            }
            return node.key + ":" + node.value;
        }
    }

    public static void main(String[] args) {
        SkipList<String> skipList = new SkipList<>();
        skipList.add(new SkipNode<>(4, "zs"));
        skipList.add(new SkipNode<>(1, "ls"));
        skipList.add(new SkipNode<>(6, "ld"));
        skipList.add(new SkipNode<>(7, "fa"));
        skipList.add(new SkipNode<>(3, "gf"));
        skipList.add(new SkipNode<>(9, "hg"));
        skipList.add(new SkipNode<>(5, "te"));

        System.out.println("删除之前=========");
        printSkipList(skipList.head);

        skipList.delete(5);
        System.out.println("删除之后=========");
        printSkipList(skipList.head);
    }

}
